/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30/FONT#10=ZERO30
␈↓ α∧␈↓␈↓ u1























␈↓ α∧␈↓α␈↓ αPCIRCUMSCRIPTION INDUCTION - A WAY OF JUMPING TO CONCLUSIONS

␈↓ α∧␈↓Abstract:␈αHumans␈αand␈αintelligent␈αcomputer␈αprograms␈αmust␈αoften␈αjump␈αto␈αthe␈αconclusion␈α
that␈αthe
␈↓ α∧␈↓objects␈αthey␈αknow␈αabout␈αare␈αthe␈αonly␈αobjects␈αinvolved␈αin␈αa␈αproblem.␈α ␈↓↓Circumscription␈αinduction␈↓␈αis
␈↓ α∧␈↓one formalization of this kind of approximate reasoning.

␈↓ α∧␈↓NOTE:␈α⊂In␈α⊂the␈α⊂body␈α∂of␈α⊂the␈α⊂current␈α⊂version␈α∂of␈α⊂this␈α⊂paper,␈α⊂the␈α∂term␈α⊂␈↓↓minimal␈α⊂inference␈↓␈α⊂is␈α∂used
␈↓ α∧␈↓instead of ␈↓↓circumscription induction␈↓.  This will be changed in subsequent versions.
␈↓ α∧␈↓␈↓ εddraft␈↓ u2


␈↓ α∧␈↓αMinimal entailment

␈↓ α∧␈↓␈↓ αT␈↓↓Minimal␈α⊂reasoning␈↓␈α⊂has␈α⊂a␈α⊂semantic␈α⊂form␈α⊂called␈α⊂␈↓↓minimal␈α⊂entailment␈↓␈α⊂and␈α⊂a␈α⊃syntactic␈α⊂form
␈↓ α∧␈↓called ␈↓↓minimal inference␈↓.  We begin with ␈↓↓minimal entailment␈↓.

␈↓ α∧␈↓␈↓ αTLet␈α
␈↓↓A␈↓␈α
be␈α
a␈α
set␈α
of␈α
sentences␈α
of␈α
first␈α
order␈α
logic␈α
and␈α
␈↓↓p␈↓␈α
a␈α
sentence.␈α
 As␈α
is␈α
customary␈α
in␈α
logic,␈α
we
␈↓ α∧␈↓say␈αthat␈α
␈↓↓A␈αentails␈αp␈↓␈α
(written␈α␈↓↓A␈α␈↓πq␈↓↓␈α
p␈↓)␈αiff␈α␈↓↓p␈↓␈α
is␈αtrue␈αin␈α
all␈αmodels␈αof␈α
␈↓↓A.␈↓␈αSuppose␈α␈↓↓M1␈↓␈α
and␈α␈↓↓M2␈↓␈αare␈α
two
␈↓ α∧␈↓models␈αof␈α
␈↓↓A.␈↓␈α␈↓↓M1␈↓␈α
is␈αcalled␈αa␈α
submodel␈αof␈α
␈↓↓M2␈↓␈α(written␈α␈↓↓M1␈α
≤␈αM2␈↓)␈α
iff␈α␈↓↓domain(M1)␈α
⊂␈αdomain(M2)␈↓,
␈↓ α∧␈↓and␈αthe␈αpredicates␈αwhen␈αapplied␈αto␈αthe␈αelements␈αof␈α␈↓↓domain(M1)␈↓␈αhave␈αthe␈αsame␈αvalues␈αin␈α␈↓↓M2␈↓␈αthat
␈↓ α∧␈↓they␈αhave␈αin␈α␈↓↓M1.␈↓␈α␈↓↓M␈↓␈αis␈α
called␈αa␈αminimal␈αmodel␈αof␈α␈↓↓A␈↓␈αiff␈α
it␈αhas␈αno␈αproper␈αsubmodels.␈α We␈αsay␈α
that
␈↓ α∧␈↓␈↓↓A␈↓␈α⊂␈↓↓minimally␈α⊂entails␈α⊂p␈↓␈α∂(written␈α⊂␈↓↓A␈α⊂␈↓πq␈↓βm␈↓↓␈α⊂p␈↓)␈α⊂iff␈α∂␈↓↓p␈↓␈α⊂is␈α⊂true␈α⊂in␈α⊂all␈α∂minimal␈α⊂models␈α⊂of␈α⊂␈↓↓A.␈α⊂ ␈↓␈α∂Minimal
␈↓ α∧␈↓entailment␈α
is␈α
not␈α
equivalent␈α∞to␈α
deduction␈α
or␈α
ordinary␈α
entailment␈α∞in␈α
any␈α
logical␈α
system.␈α∞ For␈α
any
␈↓ α∧␈↓form␈α∞of␈α∞deduction,␈α∂if␈α∞␈↓↓A␈α∞␈↓πr␈↓↓␈α∞p␈↓␈α∂and␈α∞␈↓↓A␈α∞⊂␈α∞B␈↓,␈α∂then␈α∞␈↓↓B␈α∞␈↓πr␈↓↓␈α∞p␈↓.␈α∂ We␈α∞may␈α∞call␈α∞this␈α∂property␈α∞␈↓↓monotonicity␈↓.
␈↓ α∧␈↓Exactly␈αthe␈αsame␈αproof␈αthat␈αproved␈α␈↓↓p␈↓␈αfrom␈α␈↓↓A␈↓␈αwill␈αprove␈αit␈αfrom␈α␈↓↓B.␈↓␈αEntailment␈αis␈αalso␈αmonotonic;
␈↓ α∧␈↓if␈α␈↓↓p␈↓␈αis␈αtrue␈αin␈αall␈αmodels␈αof␈α␈↓↓A,␈↓␈αit␈αis␈αtrue␈αin␈αall␈αmodels␈αof␈α␈↓↓B,␈↓␈αbecause␈αthe␈αlatter␈αare␈αa␈αsubset␈αof␈α
the
␈↓ α∧␈↓models␈α∞of␈α∂␈↓↓A.␈↓␈α∞However,␈α∂minimal␈α∞entailment␈α∂is␈α∞not␈α∞monotonic.␈α∂ Namely,␈α∞consider␈α∂the␈α∞null␈α∂set␈α∞of
␈↓ α∧␈↓sentences.␈α
 Its␈α∞minimal␈α
model␈α
is␈α∞a␈α
domain␈α
with␈α∞one␈α
element␈α
(in␈α∞most␈α
formalizations)␈α
so␈α∞that␈α
the
␈↓ α∧␈↓sentence␈α∂␈↓↓∀x y.x = y␈↓␈α∞is␈α∂minimally␈α∂entailed␈α∞by␈α∂the␈α∞null␈α∂set.␈α∂ However,␈α∞the␈α∂set␈α∞␈↓↓B␈↓␈α∂consisting␈α∂of␈α∞the
␈↓ α∧␈↓negation␈αof␈αthis␈αsentence␈αcertainly␈αcontains␈αthe␈αnull␈αset.␈α Note␈αalso␈αthat␈αminimal␈αentailment␈αis␈αnot
␈↓ α∧␈↓transitive; we can have ␈↓↓p ␈↓πq␈↓↓ q␈↓ and ␈↓↓p ␈↓πq␈↓↓ q␈↓ without having ␈↓↓p ␈↓πq␈↓↓ q␈↓.

␈↓ α∧␈↓␈↓ αTHere␈α
are␈α
some␈α
mathematical␈α
examples.␈α
 The␈α
minimal␈α
model␈α
of␈α
the␈α
Peano␈α∞axioms␈α
without
␈↓ α∧␈↓the␈αschema␈αof␈α
induction␈αis␈αthe␈α
standard␈αmodel␈αof␈α
the␈αintegers␈αprovided␈α
the␈αconstant␈α0␈αis␈α
explicitly
␈↓ α∧␈↓mentioned.␈α The␈αsystem␈αconsisting␈αonly␈αof␈αthe␈αaxioms␈αfor␈αthe␈α␈↓↓successor␈↓␈αoperation␈αomitting␈αaxioms
␈↓ α∧␈↓for␈α0␈α
has␈αno␈αminimal␈α
model,␈αbecause␈αany␈α
model␈αhas␈αa␈α
submodel.␈α There␈αis␈α
also␈αno␈αminimal␈α
model
␈↓ α∧␈↓if␈α
0␈αis␈α
characterized␈α
only␈αby␈α
an␈αexistential␈α
axiom,␈α
␈↓↓∃z.∀x.successor x ≠ z␈↓.␈α The␈α
minimal␈α
model␈αof
␈↓ α∧␈↓the␈α
axioms␈α
for␈α
group␈α
theory␈α
is␈α
the␈α
group␈α
of␈α
one␈α
element.␈α
 If␈α
we␈α
add␈α
a␈α
sentence␈α
asserting␈αthat␈α
there
␈↓ α∧␈↓is␈αmore␈αthan␈αone␈αelement,␈αthen␈αthe␈αminimal␈αmodels␈αare␈αthe␈αcyclic␈αgroups␈αof␈αprime␈αorder␈α
and␈αthe
␈↓ α∧␈↓infinite cyclic group.



␈↓ α∧␈↓αMinimal inference.

␈↓ α∧␈↓␈↓ αTMinimal␈α
entailment␈α
is␈α
a␈α
semantic␈α
mode␈α∞of␈α
reasoning␈α
and␈α
is␈α
in␈α
general␈α∞infinitary.␈α
 Indeed,
␈↓ α∧␈↓since␈αthe␈αminimal␈α
model␈αof␈αthe␈α
usual␈αfirst␈αorder␈αaxioms␈α
for␈αthe␈αintegers␈α
is␈αthe␈α␈↓↓standard␈αmodel␈↓,␈α
the
␈↓ α∧␈↓minimal␈α∞consequences␈α∞of␈α∞the␈α∞axioms␈α∞are␈α∞just␈α∞the␈α∞true␈α∞sentences␈α∞of␈α∞arithmetic,␈α∞and␈α∞this␈α∂set␈α∞isn't
␈↓ α∧␈↓recursively␈α
enumerable␈αor␈α
even␈α
arithmetic.␈α There␈α
is,␈α
however,␈αa␈α
corresponding␈α
finitary␈αsyntactic
␈↓ α∧␈↓mode␈α
of␈α
reasoning.␈α Since␈α
by␈α
G␈↓
:␈↓odel's␈α
theorem␈αit␈α
won't␈α
be␈α
complete,␈αthere␈α
will␈α
be␈α
stronger␈αmodes␈α
of
␈↓ α∧␈↓reasoning, and the correspondence with minimal entailment won't be exact.

␈↓ α∧␈↓␈↓ αTThe␈α
idea␈α∞is␈α
to␈α∞imitate␈α
the␈α∞axiom␈α
schema␈α
of␈α∞induction␈α
of␈α∞Peano␈α
arithmetic.␈α∞ Let␈α
␈↓↓A␈↓␈α∞be␈α
the
␈↓ α∧␈↓conjunction␈α
of␈αa␈α
certain␈α
subset␈αof␈α
our␈α
axioms␈αcalled␈α
the␈α
primary␈αaxioms.␈α
 The␈α
criterion␈αfor␈α
calling
␈↓ α∧␈↓some␈α∞axioms␈α∂primary␈α∞and␈α∞others␈α∂secondary␈α∞is␈α∞not␈α∂yet␈α∞entirely␈α∞clear,␈α∂but␈α∞some␈α∂separation␈α∞seems
␈↓ α∧␈↓desirable.␈α
 Let␈α
␈↓↓A␈↓	␈↓#
F␈↓#␈↓␈α
be␈α
the␈α
result␈α
of␈α
relativizing␈α␈↓↓A␈↓␈α
with␈α
respect␈α
to␈α
the␈α
predicate␈α
parameter␈α
␈↓	F␈↓.␈α (␈↓↓A␈↓	␈↓#
F␈↓#␈↓␈α
is
␈↓ α∧␈↓obtained␈α∞from␈α∞␈↓↓A␈↓␈α∞by␈α∂replacing␈α∞every␈α∞universal␈α∞quantifier␈α∂␈↓↓∀x␈↓␈α∞by␈α∞␈↓↓∀x.␈↓	F␈↓↓(x) ⊃␈↓␈α∞and␈α∂every␈α∞existential
␈↓ α∧␈↓quantifier␈α
␈↓↓∃x␈↓␈α
by␈α∞␈↓↓∃x.␈↓	F␈↓↓(x) ∧␈↓.␈α
 For␈α
each␈α
constant␈α∞␈↓↓a␈↓␈α
appearing␈α
in␈α
␈↓↓A,␈↓␈α∞we␈α
must␈α
adjoin␈α
␈↓	F␈↓↓(a)␈↓␈α∞and␈α
for
␈↓ α∧␈↓each function symbol ␈↓↓f,␈↓ we must adjoin the axiom ␈↓↓∀x.(␈↓	F␈↓↓(x) ⊃ ␈↓	F␈↓↓(f(x))␈↓)).  We introduce the schema

␈↓ α∧␈↓␈↓ αT␈↓↓A␈↓	␈↓#
F␈↓#␈↓↓ ⊃ ∀x.␈↓	F␈↓↓(x)␈↓
␈↓ α∧␈↓␈↓ εddraft␈↓ u3


␈↓ α∧␈↓which␈α∞we␈α∞call␈α∂␈↓↓the␈α∞minimal␈α∞completion␈α∂schema␈↓␈α∞of␈α∞␈↓↓A␈↓␈α∂and␈α∞write␈α∞␈↓↓MCS(A)␈↓.␈α∂ We␈α∞will␈α∞call␈α∂the␈α∞system
␈↓ α∧␈↓obtained␈αby␈αadjoining␈αthe␈αschema␈α␈↓↓MCS(A)␈↓␈αto␈αthe␈αaxiom␈α␈↓↓A␈↓␈αthe␈α␈↓↓minimal␈αcompletion␈αof␈αA␈↓,␈αwriting␈α
it
␈↓ α∧␈↓␈↓↓MC(A)␈↓.␈α
 ␈↓↓MCS(A)␈↓␈α
is␈α∞an␈α
attempt␈α
to␈α∞assert␈α
that␈α
the␈α
only␈α∞objects␈α
are␈α
those␈α∞required␈α
to␈α
exist␈α∞by␈α
the
␈↓ α∧␈↓axioms␈α␈↓↓A.␈α ␈↓␈αHere␈αis␈αa␈αtrivial␈αexample␈αof␈αa␈αminimal␈αcompletion.␈α Suppose␈αwe␈αhave␈αa␈αsingle␈αaxiom
␈↓ α∧␈↓␈↓↓ok(a)␈↓␈α
in␈α
our␈α
primary␈α
set.␈α
 Its␈α
relativization␈α
will␈α
be␈α
␈↓	F␈↓↓(a) ∧ ok(a)␈↓.␈α
 The␈α
minimal␈α
completion␈α
schema␈α
is
␈↓ α∧␈↓then

␈↓ α∧␈↓␈↓ αT␈↓	F␈↓↓(a) ∧ ok(a) ⊃ ∀x.␈↓	F␈↓↓(x)␈↓.

␈↓ α∧␈↓If␈α
we␈αsubstitute␈α
␈↓↓λx.(x = a)␈↓␈αfor␈α
␈↓	F␈↓␈αin␈α
the␈αschema␈α
we␈αcan␈α
conclude␈α␈↓↓∀x.(x = a)␈↓␈α
which␈αcharacterizes␈α
the
␈↓ α∧␈↓minimal␈αmodel␈α
of␈αthat␈αaxiom.␈α
 Indeed,␈αMartin␈αDavis␈α
showed␈αme␈αthat␈α
if␈αevery␈αmodel␈α
of␈α␈↓↓A␈↓␈α
has␈αa
␈↓ α∧␈↓minimal␈αsubmodel␈αand␈αa␈αsentence␈α␈↓	f␈↓␈αis␈αtrue␈αin␈αany␈αsupermodel␈αof␈αany␈αmodel␈αof␈α␈↓	f␈↓,␈αthen␈α␈↓	f␈↓␈αis␈αtrue
␈↓ α∧␈↓in all minimal models of ␈↓↓A␈↓ iff it is provable in the minimal completion of ␈↓↓A.␈↓

␈↓ α∧␈↓␈↓ αTLet␈α␈↓↓s1␈↓␈α
be␈αthe␈αsentence␈α
␈↓↓∀x.ok(x) = p␈↓.␈α ␈↓↓p␈↓␈α
is␈αprovable␈αin␈α
␈↓↓MC({ok(a)} ∪ s1␈↓,␈αbut␈α
it␈αis␈αnot␈α
provable
␈↓ α∧␈↓in␈α
␈↓↓MC({ok(a) ∧ s1}␈↓,␈α
because␈α
the␈αlater␈α
admits␈α
minimal␈α
models␈αin␈α
which␈α
␈↓↓p␈↓␈α
is␈αfalse␈α
and␈α
there␈α
is␈αan
␈↓ α∧␈↓individual␈α␈↓↓b␈↓␈α
such␈αthat␈α␈↓↓¬ok(b).␈↓␈α
Therefore,␈αit␈α
seems␈αthat␈αwe␈α
have␈αto␈αdivide␈α
our␈αsentences␈α
into␈αtwo
␈↓ α∧␈↓groups␈α
if␈α
we␈α
want␈α
minimal␈αinference␈α
to␈α
be␈α
useful␈α
-␈αa␈α
primary␈α
group␈α
whose␈α
minimal␈αcompletion
␈↓ α∧␈↓we␈α∂form,␈α⊂and␈α∂a␈α⊂secondary␈α∂group␈α⊂which␈α∂is␈α∂used␈α⊂but␈α∂which␈α⊂is␈α∂not␈α⊂completed.␈α∂ The␈α⊂criteria␈α∂for
␈↓ α∧␈↓deciding␈α∞in␈α
which␈α∞group␈α
to␈α∞put␈α
a␈α∞fact␈α
are␈α∞determined␈α
by␈α∞how␈α
we␈α∞want␈α
Occam's␈α∞razor␈α∞to␈α
work.
␈↓ α∧␈↓We hope to clarify this in a later version of this paper.

␈↓ α∧␈↓␈↓ αTWe␈α
can␈α
form␈α
the␈α
minimal␈α
completion␈α
of␈α
the␈α
algebraic␈α
Peano␈α
axioms␈α
as␈α
follows:␈α∞We␈α
write
␈↓ α∧␈↓the axioms

␈↓ α∧␈↓1)␈↓ αt ␈↓↓∀n.n' ≠ 0␈↓,

␈↓ α∧␈↓2)␈↓ αt ␈↓↓∀n.(n')␈↓∧-␈↓↓ = n␈↓,

␈↓ α∧␈↓and

␈↓ α∧␈↓3)␈↓ αt ␈↓↓∀n.(n ≠ 0 ⊃ n␈↓∧-␈↓↓' = n)␈↓,

␈↓ α∧␈↓where␈α⊂␈↓↓n'␈↓␈α⊂denotes␈α⊂the␈α⊂successor␈α⊂of␈α⊂␈↓↓n␈↓␈α⊂and␈α⊂␈↓↓n␈↓∧-␈↓␈α⊂denotes␈α⊂the␈α⊂predecessor␈α⊂of␈α⊂␈↓↓n␈↓.␈α⊃ The␈α⊂minimization
␈↓ α∧␈↓schema of this set of axioms is

␈↓ α∧␈↓4)␈↓ αt␈α␈↓↓␈↓	F␈↓↓(0)␈α∧␈α∀n.(␈↓	F␈↓↓(n)␈α⊃␈α␈↓	F␈↓↓(n'))␈α∧␈α∀n.(␈↓	F␈↓↓(n)␈α⊃␈α␈↓	F␈↓↓(n␈↓∧-␈↓↓))␈α∧␈α∀n.(␈↓	F␈↓↓(n)␈α⊃␈αn'␈α≠␈α0)␈α∧␈α∀n.(␈↓	F␈↓↓(n)␈α⊃␈α(n')␈↓∧-␈↓↓␈α=
␈↓ α∧␈↓↓n) ∧ ∀n.(␈↓	F␈↓↓(n) ⊃ (n≠0 ⊃ (n␈↓∧-␈↓↓)' = n))) ⊃ ∀n.␈↓	F␈↓↓(n)␈↓.

␈↓ α∧␈↓␈↓ αTThis␈αis␈αmuch␈αlonger␈α
than␈αthe␈αusual␈αschema␈α
of␈αinduction,␈αbut␈αcan␈α
be␈αshown␈αequivalent␈αto␈α
it.
␈↓ α∧␈↓Notice␈αthat␈αthe␈αconjuncts␈αin␈αthe␈αpremiss␈αthat␈αrelativize␈αthe␈αaxioms␈α(1)-(3)␈αare␈αredundant;␈αbecause
␈↓ α∧␈↓since␈α∂they␈α∂contain␈α⊂only␈α∂universal␈α∂quantifiers,␈α⊂they␈α∂are␈α∂weaker␈α⊂than␈α∂the␈α∂axioms␈α⊂they␈α∂relativize.
␈↓ α∧␈↓Thus␈αPeano␈αarithmetic␈αis␈αthe␈αminimal␈αcompletion␈αof␈αits␈αalgebraic␈αsubsystem.␈α As␈αusual,␈αwhen␈αthe
␈↓ α∧␈↓axioms␈αadmit␈α
only␈αinfinite␈α
models,␈αthe␈α
schema␈αwill␈α
not␈αbe␈α
sufficient␈αto␈α
enforce␈αthe␈αminimal␈α
model,
␈↓ α∧␈↓and␈αthere␈αwill␈αalso␈αbe␈α␈↓↓non-standard␈↓␈αmodels.␈α Martin␈αDavis␈αhas␈αalso␈αshown␈αthat␈αif␈α0␈αis␈α
introduced
␈↓ α∧␈↓through␈α∞an␈α∞existential␈α∞axiom␈α∞rather␈α∞than␈α∂as␈α∞a␈α∞constant,␈α∞the␈α∞minimal␈α∞completion␈α∂is␈α∞inconsistent;
␈↓ α∧␈↓this corresponds to the fact that this system has no minimal model.
␈↓ α∧␈↓␈↓ εddraft␈↓ u4


␈↓ α∧␈↓αApplications

␈↓ α∧␈↓␈↓ αTWe␈α⊂envisage␈α⊂using␈α⊂minimal␈α⊂inference␈α⊂in␈α⊂AI␈α∂as␈α⊂follows:␈α⊂Suppose␈α⊂a␈α⊂system␈α⊂has␈α⊂a␈α∂certain
␈↓ α∧␈↓collection␈α∞of␈α∞facts.␈α∞ It␈α∞may␈α∞or␈α∂may␈α∞not␈α∞have␈α∞all␈α∞the␈α∞relevant␈α∂facts,␈α∞but␈α∞it␈α∞is␈α∞reasonable␈α∞for␈α∂it␈α∞to
␈↓ α∧␈↓conjecture␈α∞that␈α∞does␈α∞and␈α
examine␈α∞the␈α∞consequences␈α∞of␈α
the␈α∞conjecture.␈α∞ The␈α∞minimal␈α
completion
␈↓ α∧␈↓axiom␈α
for␈αa␈α
set␈α
of␈αstatements␈α
is␈α
an␈αexpression␈α
of␈α
the␈αhypothesis␈α
that␈α
the␈αonly␈α
objects␈α
that␈αexist␈α
are
␈↓ α∧␈↓those␈α⊃which␈α⊂must␈α⊃exist␈α⊂on␈α⊃the␈α⊂basis␈α⊃of␈α⊃these␈α⊂statements.␈α⊃ In␈α⊂order␈α⊃to␈α⊂make␈α⊃this␈α⊃workable␈α⊂in
␈↓ α∧␈↓practice,␈αit␈αwill␈αbe␈αnecessary␈αto␈αapply␈αminimal␈αcompletion␈αto␈αsubsets␈αof␈αthe␈αfacts;␈αdifferent␈αsubsets
␈↓ α∧␈↓will␈αgive␈α
rise␈αto␈α
different␈αconjectures.␈α Moreover,␈α
we␈αwill␈α
need␈αto␈αapply␈α
the␈αrelativization␈α
to␈αonly
␈↓ α∧␈↓some␈α
of␈α∞the␈α
sorts␈α
of␈α∞individuals,␈α
so␈α
that␈α∞we␈α
can␈α
remain␈α∞non-committal␈α
about␈α
whether␈α∞there␈α
are
␈↓ α∧␈↓more of certain sorts than our axioms prove to exist.

␈↓ α∧␈↓␈↓ αTAn␈α∩example␈α∩that␈α∩has␈α∩been␈α∩much␈α∩studied␈α⊃in␈α∩AI␈α∩and␈α∩which␈α∩contains␈α∩enough␈α∩detail␈α⊃to
␈↓ α∧␈↓illustrate various issues is the ␈↓↓missionaries and cannibals␈↓ problem, stated as follows:

␈↓ α∧␈↓␈↓ αT␈↓↓"Three␈α∪missionaries␈α∀and␈α∪three␈α∀cannibals␈α∪come␈α∀to␈α∪a␈α∪river.␈α∀ A␈α∪rowboat␈α∀that␈α∪seats␈α∀two␈α∪is
␈↓ α∧␈↓↓available.␈α
 However,␈αif␈α
the␈αcannibals␈α
ever␈αoutnumber␈α
the␈αmissionaries␈α
on␈αeither␈α
bank␈αof␈α
the␈αriver,
␈↓ α∧␈↓↓the outnumbered missionaries will be eaten.  How shall they cross the river?"␈↓.

␈↓ α∧␈↓␈↓ αTAmarel␈α⊃(1971)␈α⊃considered␈α⊃various␈α⊃representations␈α⊃of␈α⊃the␈α⊃problem␈α⊃and␈α∩discussed␈α⊃criteria
␈↓ α∧␈↓whereby␈α⊂the␈α⊃following␈α⊂representation␈α⊂is␈α⊃preferred␈α⊂for␈α⊂purposes␈α⊃of␈α⊂AI,␈α⊂because␈α⊃it␈α⊂leads␈α⊃to␈α⊂the
␈↓ α∧␈↓smallest␈αstate␈αspace␈αthat␈αmust␈αbe␈αexplored␈αto␈αfind␈αthe␈αsolution.␈α We␈αrepresent␈αa␈αstate␈αby␈αthe␈α
triplet
␈↓ α∧␈↓consisting␈α∞of␈α∞the␈α
numbers␈α∞of␈α∞missionaries,␈α
cannibals␈α∞and␈α∞boats␈α
on␈α∞the␈α∞initial␈α
bank␈α∞of␈α∞the␈α
river.
␈↓ α∧␈↓The␈αinitial␈αconfiguration␈α
is␈α331,␈αthe␈αdesired␈α
final␈αconfiguration␈αis␈α000,␈α
and␈αone␈αsolution␈α
is␈αgiven
␈↓ α∧␈↓by the sequence (331,220,321,300,311,110,221,020,031,010,021,000) of states.

␈↓ α∧␈↓␈↓ αTWe␈α⊂are␈α⊂not␈α⊂presently␈α⊂concerned␈α⊂with␈α⊂the␈α⊂heuristics␈α⊂of␈α⊂the␈α⊂problem␈α⊂but␈α⊂rather␈α⊂with␈α⊂the
␈↓ α∧␈↓correctness␈αof␈αthe␈αreasoning␈αthat␈α
goes␈αfrom␈αthe␈αEnglish␈αstatement␈α
of␈αthe␈αproblem␈αto␈αAmarel's␈α
state
␈↓ α∧␈↓space␈α
representation.␈α
 A␈α∞generally␈α
intelligent␈α
computer␈α∞program␈α
should␈α
be␈α∞able␈α
to␈α
carry␈α∞out␈α
this
␈↓ α∧␈↓reasoning.␈α⊃ Of␈α∩course␈α⊃there␈α∩are␈α⊃the␈α⊃well␈α∩known␈α⊃difficulties␈α∩in␈α⊃making␈α∩computers␈α⊃understand
␈↓ α∧␈↓English,␈α⊃but␈α⊃suppose␈α⊃the␈α⊃English␈α⊃sentences␈α⊃describing␈α⊃the␈α⊃problem␈α⊃have␈α⊃already␈α⊃been␈α⊃rather
␈↓ α∧␈↓directly␈α⊂translated␈α⊂into␈α⊂first␈α⊂order␈α⊂logic.␈α⊂ The␈α⊂correctness␈α⊂of␈α⊂Amarel's␈α⊂representation␈α⊂is␈α⊃not␈α⊂an
␈↓ α∧␈↓ordinary logical consequence of these sentences for two further reasons.

␈↓ α∧␈↓␈↓ αTFirst,␈α∞nothing␈α∞has␈α∞been␈α∞stated␈α∞about␈α∞the␈α∞properties␈α∞of␈α∞boats␈α∞or␈α∞even␈α∞the␈α∞fact␈α∞that␈α
rowing
␈↓ α∧␈↓across␈α∞the␈α∞river␈α
doesn't␈α∞change␈α∞the␈α∞numbers␈α
of␈α∞missionaries␈α∞or␈α∞cannibals␈α
or␈α∞the␈α∞capacity␈α∞of␈α
the
␈↓ α∧␈↓boat.␈α These␈αare␈αa␈αconsequence␈αof␈αcommon␈αsense␈αknowledge,␈αso␈αlet␈αus␈αimagine␈αthat␈αcommon␈αsense
␈↓ α∧␈↓knowledge, or at least the relevant part of it, is also expressed in first order logic.

␈↓ α∧␈↓␈↓ αTThe␈α∩second␈α⊃reason␈α∩we␈α⊃can't␈α∩␈↓↓deduce␈↓␈α∩the␈α⊃propriety␈α∩of␈α⊃Amarel's␈α∩representation␈α∩is␈α⊃deeper.
␈↓ α∧␈↓Imagine␈α
giving␈α
someone␈α
the␈α
problem,␈α
and␈α
after␈αhe␈α
puzzles␈α
for␈α
a␈α
while,␈α
he␈α
suggests␈αgoing␈α
upstream
␈↓ α∧␈↓half␈α
a␈α
mile␈α
and␈α
crossing␈α
on␈α
a␈α
bridge.␈α∞ "What␈α
bridge",␈α
you␈α
say.␈α
 "No␈α
bridge␈α
is␈α
mentioned␈α∞in␈α
the
␈↓ α∧␈↓statement␈αof␈αthe␈α
problem."␈αAnd␈αthis␈α
dunce␈αreplies,␈α"Well,␈α
it␈αisn't␈αstated␈α
that␈αthere␈αisn't␈α
a␈αbridge".
␈↓ α∧␈↓You␈αlook␈αat␈αthe␈αEnglish␈αand␈αeven␈αat␈αthe␈αtranslation␈αof␈αthe␈αEnglish␈αinto␈αfirst␈αorder␈αlogic,␈αand␈αyou
␈↓ α∧␈↓must␈α∂admit␈α∞that␈α∂it␈α∞isn't␈α∂stated␈α∂that␈α∞there␈α∂is␈α∞no␈α∂bridge.␈α∂ So␈α∞you␈α∂modify␈α∞the␈α∂problem␈α∂to␈α∞exclude
␈↓ α∧␈↓bridges␈α∞and␈α∞pose␈α∂it␈α∞again,␈α∞and␈α∂the␈α∞dunce␈α∞proposes␈α∂a␈α∞helicopter,␈α∞and␈α∂after␈α∞you␈α∞exclude␈α∂that␈α∞he
␈↓ α∧␈↓proposes␈αa␈α
winged␈αhorse␈αor␈α
that␈αthe␈α
others␈αhang␈αonto␈α
the␈αoutside␈α
of␈αthe␈αboat␈α
while␈αtwo␈αrow.␈α
 You
␈↓ α∧␈↓now␈α
see␈α
that␈α
while␈α
a␈α
dunce,␈α
he␈α
is␈α
an␈αinventive␈α
dunce,␈α
and␈α
you␈α
despair␈α
of␈α
getting␈α
him␈α
to␈αaccept␈α
the
␈↓ α∧␈↓problem␈αin␈α
the␈αproper␈α
puzzler's␈αspirit␈α
and␈αtell␈α
him␈αthe␈α
solution.␈α You␈α
are␈αfurther␈α
annoyed␈αwhen
␈↓ α∧␈↓␈↓ εddraft␈↓ u5


␈↓ α∧␈↓he␈αattacks␈αyour␈αsolution␈αon␈αthe␈αgrounds␈αthat␈αthe␈αboat␈αmight␈αhave␈αa␈αleak␈αor␈αnot␈αhave␈αoars.␈α After
␈↓ α∧␈↓you␈αrectify␈αthat␈αomission,␈αhe␈αsuggests␈αthat␈αa␈αsea␈αmonster␈αmay␈αswim␈αup␈αthe␈αriver␈αand␈αmay␈αswallow
␈↓ α∧␈↓the␈αboat.␈α
 Again␈αyou␈α
are␈αfrustrated,␈α
and␈αyou␈α
look␈αfor␈α
a␈αmode␈α
of␈αreasoning␈α
that␈αwill␈α
settle␈αhis␈α
hash
␈↓ α∧␈↓once and for all.

␈↓ α∧␈↓␈↓ αTMinimal␈αmodels␈α
and␈αminimal␈αinference␈α
may␈αgive␈αthe␈α
solution.␈α In␈αa␈α
minimal␈αmodel␈α
of␈αthe
␈↓ α∧␈↓first␈α∞order␈α
logic␈α∞statement␈α
of␈α∞the␈α
problem,␈α∞there␈α∞is␈α
no␈α∞bridge␈α
or␈α∞helicopter.␈α
 "Ah",␈α∞you␈α∞say,␈α
"but
␈↓ α∧␈↓there␈αaren't␈αany␈αoars␈αeither".␈α No,␈αwe␈αget␈αout␈αof␈αthat␈αas␈αfollows:␈αIt␈αis␈αa␈αpart␈αof␈αcommon␈αknowledge
␈↓ α∧␈↓that␈αa␈αboat␈αcan␈αbe␈αused␈αto␈αcross␈αa␈αriver␈α␈↓↓unless␈αthere␈αis␈αsomething␈αwrong␈αwith␈αit␈αor␈α
something␈αelse
␈↓ α∧␈↓↓prevents␈αusing␈αit␈↓,␈αand␈αin␈αthe␈αminimal␈αmodel␈αof␈αthe␈αfacts␈αthere␈αdoesn't␈αexist␈αsomething␈αwrong␈α
with
␈↓ α∧␈↓the boat, and there isn't anything else to prevent its use.

␈↓ α∧␈↓␈↓ αTThe␈α∪non-monotonic␈α∩character␈α∪of␈α∩minimal␈α∪reasoning␈α∪is␈α∩just␈α∪what␈α∩we␈α∪want␈α∪here.␈α∩ The
␈↓ α∧␈↓statement,␈α␈↓↓"There␈αis␈αa␈αbridge␈α
a␈αmile␈αupstream."␈↓␈αdoesn't␈αcontradict␈α
the␈αtext␈αof␈αthe␈αproblem,␈α
but␈αits
␈↓ α∧␈↓addition invalidates the Amarel representation.

␈↓ α∧␈↓␈↓ αTIn␈α∞the␈α∞usual␈α∞sort␈α∞of␈α∞puzzle,␈α∞there␈α∞can␈α∞be␈α∞no␈α∞additional␈α∞source␈α∞of␈α∞information␈α∞beyond␈α∞the
␈↓ α∧␈↓puzzle␈αand␈αcommon␈αsense␈α
knowledge.␈α Therefore,␈αthe␈αconvention␈α
can␈αbe␈αexplicated␈αas␈α
taking␈αthe
␈↓ α∧␈↓minimal␈α∞completion␈α∞of␈α∞the␈α
puzzle␈α∞statement␈α∞and␈α∞a␈α∞certain␈α
part␈α∞of␈α∞common␈α∞sense␈α∞knowledge.␈α
 If
␈↓ α∧␈↓one␈α
really␈α
were␈αsitting␈α
by␈α
a␈α
river␈αbank␈α
and␈α
these␈αsix␈α
people␈α
came␈α
by␈αand␈α
posed␈α
their␈αproblem,␈α
one
␈↓ α∧␈↓wouldn't␈α∂immediately␈α∞take␈α∂the␈α∞minimal␈α∂completion␈α∂for␈α∞granted,␈α∂but␈α∞one␈α∂would␈α∞consider␈α∂it␈α∂as␈α∞a
␈↓ α∧␈↓hypothesis.

␈↓ α∧␈↓␈↓ αTAt␈αfirst␈αI␈αconsidered␈αthis␈αsolution␈αtoo␈αad␈αhoc␈αto␈αbe␈αacceptable,␈αbut␈αI␈αam␈αnow␈αconvinced␈αthat
␈↓ α∧␈↓it␈αis␈αa␈αcorrect␈αexplication␈αof␈αthe␈α␈↓↓normal␈↓␈αsituation,␈αe.g.␈αunless␈αsomething␈αabnormal␈αexists,␈αan␈αobject
␈↓ α∧␈↓can be used to carry out its normal function.

␈↓ α∧␈↓␈↓ αTSome␈α∂have␈α∂suggested␈α∂that␈α∂the␈α∂difficulties␈α∂might␈α∂be␈α∂avoided␈α∂by␈α∂introducing␈α∂probabilities.
␈↓ α∧␈↓They␈α∞suggest␈α∞that␈α∞the␈α∂existence␈α∞of␈α∞a␈α∞bridge␈α∞is␈α∂improbable.␈α∞ Well␈α∞the␈α∞whole␈α∂situation␈α∞involving
␈↓ α∧␈↓cannibals␈α∂with␈α⊂the␈α∂postulated␈α⊂properties␈α∂is␈α⊂so␈α∂improbable␈α⊂that␈α∂it␈α⊂is␈α∂hard␈α⊂to␈α∂take␈α⊂seriously␈α∂the
␈↓ α∧␈↓conditional␈α⊃probability␈α⊃of␈α∩a␈α⊃bridge␈α⊃given␈α⊃the␈α∩hypotheses.␈α⊃ Moreover,␈α⊃we␈α⊃mentally␈α∩propose␈α⊃to
␈↓ α∧␈↓ourselves␈α→the␈α→normal␈α→non-bridge␈α→non-sea␈α→monster␈α→interpretation␈α→␈↓↓before␈↓␈α→considering␈α_these
␈↓ α∧␈↓extraneous␈α
possibilities,␈α
let␈α
alone␈α
their␈α
probabilities,␈α
i.e.␈α
we␈α
usually␈α
don't␈α
even␈α
introduce␈α
the␈α
sample
␈↓ α∧␈↓space␈αin␈αwhich␈αthese␈αpossibilities␈αare␈αassigned␈αwhatever␈αprobabilities␈αone␈αmight␈αconsider␈αthem␈αto
␈↓ α∧␈↓have.␈α Therefore,␈αregardless␈αof␈αour␈αknowledge␈αof␈αprobabilities,␈αwe␈αneed␈αa␈αway␈αof␈αformulating␈αthe
␈↓ α∧␈↓normal␈α
situation␈α
from␈α
the␈α
statement␈α
of␈α
the␈α
facts,␈α
and␈α
the␈α
minimal␈α
completion␈α
axioms␈α
seems␈α
to␈α
be␈α
a
␈↓ α∧␈↓method.

␈↓ α∧␈↓␈↓ αTOf␈αcourse,␈αwe␈αhaven't␈αgiven␈αan␈αexpression␈αof␈αcommon␈αsense␈αknowledge␈αin␈αa␈αform␈αthat␈αsays
␈↓ α∧␈↓a␈α∂boat␈α∂can␈α⊂be␈α∂used␈α∂to␈α⊂cross␈α∂rivers␈α∂unless␈α∂there␈α⊂is␈α∂something␈α∂wrong␈α⊂with␈α∂it.␈α∂ In␈α⊂particular,␈α∂we
␈↓ α∧␈↓haven't␈α⊂introduced␈α⊂into␈α∂our␈α⊂␈↓↓ontology␈↓␈α⊂(the␈α∂things␈α⊂that␈α⊂exist)␈α∂a␈α⊂category␈α⊂that␈α⊂includes␈α∂␈↓↓something
␈↓ α∧␈↓↓wrong␈α∞with␈α∂a␈α∞boat␈↓␈α∂or␈α∞a␈α∞category␈α∂that␈α∞includes␈α∂␈↓↓something␈α∞that␈α∞may␈α∂prevent␈α∞its␈α∂use␈↓.␈α∞ Incidentally,
␈↓ α∧␈↓once␈αwe␈αhave␈αdecided␈αto␈αadmit␈α␈↓↓something␈αwrong␈αwith␈αthe␈αboat␈↓,␈αwe␈αare␈αinclined␈αto␈αadmit␈αa␈α␈↓↓lack␈αof
␈↓ α∧␈↓↓oars␈↓␈α
as␈α
such␈α
a␈α
something␈α
and␈α
to␈α
ask␈α
questions␈α∞like,␈α
␈↓↓"Is␈α
a␈α
lack␈α
of␈α
oars␈α
all␈α
that␈α
is␈α
wrong␈α∞with␈α
the
␈↓ α∧␈↓↓boat?␈↓".

␈↓ α∧␈↓␈↓ αTI␈α∩imagine␈α∩that␈α∪many␈α∩philosophers␈α∩and␈α∩scientists␈α∪would␈α∩be␈α∩reluctant␈α∩to␈α∪introduce␈α∩such
␈↓ α∧␈↓␈↓↓things,␈↓␈α
but␈α
the␈αfact␈α
that␈α
ordinary␈α
language␈αallows␈α
␈↓↓"something␈α
wrong␈αwith␈α
the␈α
boat"␈↓␈α
suggests␈αthat
␈↓ α∧␈↓we␈α
shouldn't␈α
be␈α
hasty␈α
in␈α
excluding␈α
it.␈α
 Making␈α
a␈α
suitable␈α
formalism␈α
may␈α
be␈α
technically␈αdifficult
␈↓ α∧␈↓and philosophically problematical, but we must try.
␈↓ α∧␈↓␈↓ εddraft␈↓ u6


␈↓ α∧␈↓␈↓ αTIn␈α
compensation,␈αwe␈α
may␈α
get␈αan␈α
increased␈αability␈α
to␈α
understand␈αnatural␈α
language,␈αbecause␈α
if
␈↓ α∧␈↓natural␈αlanguage␈αadmits␈αsomething␈αlike␈αminimal␈αreasoning,␈αit␈αis␈αunderstandable␈αthat␈αwe␈αwill␈αhave
␈↓ α∧␈↓difficulty in translating it into logical formalisms that don't.

␈↓ α∧␈↓␈↓ αTThe␈α⊗possibility␈α⊗of␈α⊗forming␈α⊗minimal␈α⊗completions␈α⊗of␈α⊗various␈α⊗parts␈α⊗of␈α⊗our␈α∃knowledge
␈↓ α∧␈↓introduces␈α∂a␈α∂kind␈α∂of␈α∂fuzziness␈α∂that␈α∂I␈α∂believe␈α∂may␈α∂prove␈α∂more␈α∂fruitful␈α∂than␈α∂that␈α∂explicated␈α∂by
␈↓ α∧␈↓fuzzy set theory.


␈↓ α∧␈↓αMinimal models and minimal entailment in propositional calculus.

␈↓ α∧␈↓␈↓ αTAs␈α⊗the␈α⊗above␈α⊗indicates,␈α⊗developing␈α⊗techniques␈α⊗for␈α⊗minimal␈α⊗entailment␈α⊗and␈α⊗minimal
␈↓ α∧␈↓inference␈αand␈αaxiomatizing␈αcommon␈αsense␈αknowledge␈αin␈αa␈αform␈αsuitable␈αfor␈αcomputer␈αuse␈αwill␈αbe
␈↓ α∧␈↓difficult.␈α Therefore␈α
it␈αseems␈αworthwhile␈α
to␈αstudy␈αa␈α
propositional␈αcalculus␈αanalog␈α
of␈αthe␈αfirst␈α
order
␈↓ α∧␈↓logic situation even though we haven't found any direct applications of the propositional case.

␈↓ α∧␈↓␈↓ αTSuppose␈α
we␈α
have␈α
some␈α
facts␈α
to␈α
express␈α
but␈α
have␈α
not␈α
yet␈α
chosen␈α
a␈α∞propositional␈α
language.
␈↓ α∧␈↓Our␈α⊂first␈α⊃step␈α⊂is␈α⊃to␈α⊂introduce␈α⊃propositional␈α⊂letters␈α⊃␈↓↓p␈↓β1␈↓↓,...,p␈↓βn␈↓␈α⊂and␈α⊃to␈α⊂specify␈α⊃each␈α⊂of␈α⊃them␈α⊂as
␈↓ α∧␈↓expressing␈α⊃some␈α⊃elementary␈α⊂fact.␈α⊃ We␈α⊃call␈α⊃this␈α⊂establishing␈α⊃a␈α⊃␈↓↓propositional␈α⊃co-ordinate␈α⊂system␈↓.
␈↓ α∧␈↓Then␈αwe␈αexpress␈αthe␈αset␈α␈↓↓A␈↓␈αof␈αknown␈αfacts␈αas␈αa␈αsentence␈α␈↓↓AX␈↓␈αin␈αthis␈αco-ordinate␈αsystem.␈α A␈αmodel
␈↓ α∧␈↓of␈αthe␈αfacts␈αis␈αany␈αassignment␈αof␈αtruth␈αvalues␈αto␈αthe␈α␈↓↓p␈↓βi␈↓'s␈αthat␈αmakes␈α␈↓↓AX␈↓␈αtrue.␈α Let␈α␈↓↓M1␈↓␈αand␈α␈↓↓M2␈↓␈αbe
␈↓ α∧␈↓models of ␈↓↓AX.␈↓ We define

␈↓ α∧␈↓␈↓ αT␈↓↓M1 ≤ M2 ≡ ∀i.(true(p␈↓βi␈↓↓,M2) ⊃ true(p␈↓βi␈↓↓,M1))␈↓.

␈↓ α∧␈↓A␈α
minimal␈α
model␈α
is␈α
one␈α
that␈α
is␈α
not␈αa␈α
proper␈α
extension,␈α
i.e.␈α
a␈α
model␈α
in␈α
which␈α
(roughly␈αspeaking)␈α
as
␈↓ α∧␈↓many␈αof␈α
the␈α␈↓↓p␈↓βi␈↓s␈αas␈α
possible␈αare␈αfalse␈α
-␈αconsistent␈α
with␈αthe␈αtruth␈α
of␈α␈↓↓AX␈↓.␈α ␈↓↓Note␈α
that␈αwhile␈αthe␈α
models
␈↓ α∧␈↓↓of␈αa␈αset␈αof␈αfacts␈αare␈αindependent␈αof␈αthe␈αco-ordinate␈αsystem,␈αthe␈αminimal␈αmodels␈αdepend␈αon␈αthe␈αco-
␈↓ α∧␈↓↓ordinate␈αsystem␈↓.␈α Here␈αis␈αthe␈αmost␈αtrivial␈αexample.␈α Let␈αthere␈αbe␈αone␈αletter␈α␈↓↓p␈↓␈αrepresenting␈αthe␈αone
␈↓ α∧␈↓fact␈α∞in␈α
a␈α∞co-ordinate␈α
system␈α∞␈↓↓C,␈↓␈α
and␈α∞let␈α
␈↓↓A␈↓␈α∞be␈α
the␈α∞null␈α
set␈α∞of␈α
facts␈α∞so␈α
that␈α∞␈↓↓AX␈↓␈α
is␈α∞the␈α∞sentence␈α
␈↓↓T␈↓
␈↓ α∧␈↓(identically␈α∂true).␈α⊂ The␈α∂one␈α∂other␈α⊂co-ordinate␈α∂system␈α⊂␈↓↓C'␈↓␈α∂uses␈α∂the␈α⊂elementary␈α∂sentence␈α⊂␈↓↓p'␈↓␈α∂taken
␈↓ α∧␈↓equivalent␈α
to␈α
␈↓↓¬p␈↓.␈α
 The␈α
minimal␈α
model␈α
of␈α
␈↓↓C␈↓␈α
is␈α{¬p},␈α
and␈α
the␈α
minimal␈α
model␈α
of␈α
␈↓↓C'␈↓␈α
is␈α
{p}.␈α Since
␈↓ α∧␈↓minimal␈α∞reasoning␈α
depends␈α∞on␈α
the␈α∞co-ordinate␈α
system␈α∞and␈α
not␈α∞merely␈α
on␈α∞the␈α
facts␈α∞expressed␈α
in
␈↓ α∧␈↓the␈αaxioms,␈αthe␈αutility␈αof␈αan␈αaxiom␈αsystem␈αwill␈αdepend␈αon␈αwhether␈αits␈αminimal␈αmodels␈αexpress␈α
the
␈↓ α∧␈↓uses we wish to make of Occam's razor.

␈↓ α∧␈↓␈↓ αTA␈α∪less␈α∩trivial␈α∪example␈α∩of␈α∪minimal␈α∩entailment␈α∪is␈α∩the␈α∪following.␈α∩ The␈α∪propositional␈α∩co-
␈↓ α∧␈↓ordinate␈α
system␈α∞has␈α
basic␈α
sentences␈α∞␈↓↓p␈↓β1␈↓,␈α
␈↓↓p␈↓β2␈↓␈α
and␈α∞␈↓↓p␈↓β3␈↓,␈α
and␈α
␈↓↓AX␈α∞=␈α
p␈↓β1␈↓↓␈α
∨␈α∞p␈↓β2␈↓.␈α
 There␈α
are␈α∞two␈α
minimal
␈↓ α∧␈↓models.␈α
 ␈↓↓p␈↓β3␈↓␈α
is␈α
false␈αin␈α
both,␈α
and␈α
␈↓↓p␈↓β1␈↓␈αis␈α
false␈α
in␈α
one,␈αand␈α
␈↓↓p␈↓β2␈↓␈α
is␈α
false␈αin␈α
the␈α
other.␈α
 Thus␈α
we␈αhave
␈↓ α∧␈↓␈↓↓AX ␈↓πq␈↓βm␈↓↓ (¬(p␈↓β1␈↓↓ ∧ p␈↓β2␈↓↓) ∧ ¬p␈↓β3␈↓).

␈↓ α∧␈↓␈↓ αTNote␈α
that␈αif␈α
␈↓↓AX␈↓␈αis␈α
a␈α
conjunction␈αof␈α
certain␈αelementary␈α
sentences␈α
(some␈αof␈α
them␈αnegated),␈α
e.g.
␈↓ α∧␈↓␈↓↓AX = p␈↓β2␈↓↓ ∧ ¬p␈↓β4␈↓,␈α∂then␈α⊂there␈α∂is␈α⊂a␈α∂unique␈α⊂minimal␈α∂model,␈α⊂but␈α∂if,␈α⊂as␈α∂above,␈α⊂␈↓↓AX = p␈↓β2␈↓↓ ∨ ¬p␈↓β4␈↓,␈α∂then
␈↓ α∧␈↓there is more than one minimal model.

␈↓ α∧␈↓␈↓ αTOne may also consider extensions ␈↓↓relative␈↓ to a set ␈↓↓B␈↓ of elementary sentences.  We have

␈↓ α∧␈↓␈↓ αT␈↓↓M1 ≤ M2 (mod B) ≡ ∀p.(p ε B ∧ true(p,M1) ⊃ true(p,M2)␈↓.
␈↓ α∧␈↓␈↓ εddraft␈↓ u7


␈↓ α∧␈↓We␈α⊂can␈α⊂then␈α⊂introduce␈α⊂minimal␈α⊂models␈α⊂relative␈α⊂to␈α⊂␈↓↓B␈↓␈α⊂and␈α⊂the␈α⊂corresponding␈α⊂relative␈α∂minimal
␈↓ α∧␈↓entailment.␈α
 Thus␈α
we␈α
may␈α
care␈α
about␈α
minimality␈α∞and␈α
Occam's␈α
razor␈α
only␈α
over␈α
a␈α
certain␈α∞part␈α
of
␈↓ α∧␈↓our knowledge.

␈↓ α∧␈↓␈↓ αTNote␈α⊂that␈α⊂we␈α⊂may␈α⊂discover␈α⊂a␈α⊂set␈α⊂of␈α⊂facts␈α⊂one␈α⊂at␈α⊂a␈α⊂time␈α⊂so␈α⊂that␈α⊂we␈α⊂have␈α⊂an␈α⊂increasing
␈↓ α∧␈↓sequence␈α⊂␈↓↓A␈↓β1␈↓↓␈α⊂⊂␈α⊂A␈↓β2␈↓␈α⊂⊂␈α⊂...␈α⊂of␈α⊂sets␈α⊂of␈α⊂sentences.␈α⊂ A␈α⊂given␈α⊂sentence␈α⊂␈↓↓p␈↓␈α⊂may␈α⊂oscillate␈α⊂in␈α⊃its␈α⊂minimal
␈↓ α∧␈↓entailment␈α∂by␈α∞the␈α∂␈↓↓A␈↓βi␈↓,␈α∞e.g.␈α∂we␈α∞may␈α∂have␈α∂␈↓↓A␈↓β1␈↓π q␈↓βm␈↓↓ p␈↓,␈α∞␈↓↓A␈↓β2␈↓π q␈↓βm␈↓↓ ¬p␈↓,␈α∂neither␈α∞may␈α∂be␈α∞entailed␈α∂by␈α∂␈↓↓A␈↓β3␈↓,␈α∞etc.
␈↓ α∧␈↓The␈α
common␈α∞sense␈α
Occam's␈α∞razor␈α
conclusion␈α
about␈α∞a␈α
sentence␈α∞␈↓↓p␈↓␈α
often␈α
behaves␈α∞this␈α
way␈α∞as␈α
our
␈↓ α∧␈↓knowledge increases.
␈↓ α∧␈↓␈↓ εddraft␈↓ u8


␈↓ α∧␈↓αNotes

␈↓ α∧␈↓␈↓ αT1.␈α
There␈α
is␈α∞a␈α
relation␈α
between␈α∞minimal␈α
entailment␈α
and␈α∞the␈α
THNOT␈α
formalism␈α∞of␈α
micro-
␈↓ α∧␈↓planner.␈α (THNOT␈α␈↓↓p)␈↓␈αmeans␈αthat␈αan␈αattempt␈αto␈αprove␈α␈↓↓p␈↓␈αhas␈αfailed,␈αand␈αsuch␈αa␈αfailure␈α
to␈αprove
␈↓ α∧␈↓something␈αwrong␈α
with␈αthe␈αboat␈α
could␈αlead␈αto␈α
a␈αplan␈αto␈α
row␈αacross␈αthe␈α
river.␈α Likewise␈α
failure␈αto
␈↓ α∧␈↓prove␈αthe␈αexistence␈αof␈αa␈αbridge␈αcan␈αbe␈αused␈αto␈αgo␈αfrom␈αthe␈αfacts␈αto␈αthe␈αAmarel␈αrepresentation.␈α A
␈↓ α∧␈↓major␈α
difference␈α
is␈αthat␈α
minimal␈α
entailment␈αdoes␈α
not␈α
depend␈αon␈α
what␈α
theorem␈α
proving␈αmethods
␈↓ α∧␈↓are used.

␈↓ α∧␈↓␈↓ αT2.␈αWhen␈α
we␈αadd␈α
common␈αsense␈αknowledge␈α
or␈αgeneral␈α
scientific␈αknowledge␈α
to␈αthe␈αfacts␈α
about
␈↓ α∧␈↓a␈α∩particular␈α∩problem,␈α∩we␈α∩get␈α⊃a␈α∩huge␈α∩collection␈α∩of␈α∩facts␈α⊃with␈α∩huge␈α∩models␈α∩most␈α∩of␈α∩which␈α⊃is
␈↓ α∧␈↓irrelevant␈αto␈αthe␈αproblem.␈α
 The␈αusual␈αapproach␈αis␈α
for␈αthe␈αhuman␈αto␈α
separate␈αwhat␈αis␈αrelevant␈α
and
␈↓ α∧␈↓make␈αan␈αaxiom␈αsystem␈αcontaining␈αonly␈α
relevant␈αinformation.␈α If␈αwe␈αwant␈αa␈αcomputer␈α
program␈αto
␈↓ α∧␈↓express␈α∞what␈α∂it␈α∞knows␈α∞in␈α∂a␈α∞certain␈α∞language,␈α∂we␈α∞need␈α∞a␈α∂better␈α∞way.␈α∞ One␈α∂way␈α∞of␈α∂reducing␈α∞the
␈↓ α∧␈↓number␈αof␈α
models␈αis␈αto␈α
say␈αthat␈α
two␈αmodels␈αare␈α
equivalent␈αif␈α
they␈αare␈αthe␈α
same␈αfor␈α
certain␈αsorts
␈↓ α∧␈↓and␈αcertain␈αpredicates␈αand␈αfunctions.␈α We␈αthen␈α
work␈αwith␈αthe␈αequivalence␈αclasses␈αand␈αtry␈αto␈α
make
␈↓ α∧␈↓a␈α∞set␈α∞of␈α
sentences␈α∞involving␈α∞only␈α
the␈α∞objects␈α∞in␈α∞these␈α
sorts␈α∞and␈α∞as␈α
few␈α∞others␈α∞as␈α∞possible␈α
whose
␈↓ α∧␈↓models correspond to these equivalence classes.

␈↓ α∧␈↓␈↓ αT3.␈αIn␈αthe␈αfirst␈αorder␈α
logic␈αtheory␈αwe␈αalso␈αneed␈α
to␈αconsider␈αextensions␈αand␈αminimality␈α
relative
␈↓ α∧␈↓to a subcollection of the sorts.

␈↓ α∧␈↓␈↓ αT4.␈α∂In␈α∂the␈α∂propositional␈α∂calculus␈α∂system␈α∂we␈α∂minimize␈α∂the␈α∂set␈α∂of␈α⊂propositional␈α∂co-ordinates
␈↓ α∧␈↓assigned␈α∂␈↓αtrue␈↓␈α∂while␈α∞in␈α∂the␈α∂predicate␈α∂calculus␈α∞system␈α∂we␈α∂minimize␈α∂the␈α∞set␈α∂of␈α∂objects␈α∂asserted␈α∞to
␈↓ α∧␈↓exist.␈α
 It␈α
might␈α
be␈α
worth␈α
considering␈α
co-ordinate␈α
systems␈α
in␈α
the␈α
predicate␈α
calculus␈α
system␈α
within
␈↓ α∧␈↓which it is worthwhile to minimize the set of propositions asserted.

␈↓ α∧␈↓␈↓ αT5.␈α
Reading␈α
Hayes␈α
on␈α
frames␈α
suggests␈α
that␈α
default␈α
values␈α
in␈α
Minsky␈α
frames␈α
can␈α
be␈α
treated␈α
by
␈↓ α∧␈↓circumscription,␈α
e.g.␈α
a␈α∞house␈α
has␈α
a␈α
kitchen␈α∞unless␈α
there␈α
is␈α
a␈α∞reason␈α
why␈α
it␈α
doesn't.␈α∞ Making␈α
this
␈↓ α∧␈↓work␈αwith␈αcircumscription␈αas␈αnow␈αconceived␈αrequires␈αintroducing␈αreasons␈αas␈αentities.␈α While␈αsuch
␈↓ α∧␈↓ontological␈α
liberalism␈αis␈α
congenial,␈αwe␈α
need␈αto␈α
check␈αwhether␈α
there␈αis␈α
a␈αmore␈α
compact␈α
schema␈αor
␈↓ α∧␈↓other means of treating default values.

␈↓ α∧␈↓␈↓ αTAlternatively,␈α⊗we␈α⊗can␈α⊗try␈α∃the␈α⊗propositional␈α⊗approach␈α⊗of␈α∃minimizing␈α⊗the␈α⊗set␈α⊗of␈α∃true
␈↓ α∧␈↓propositions␈α∃and␈α∃put␈α∃␈↓↓lacks(x,Kitchen)␈↓␈α∃in␈α∃the␈α∀set␈α∃to␈α∃be␈α∃minimized.␈α∃ This␈α∃is␈α∃perhaps␈α∀clear
␈↓ α∧␈↓semantically,␈α∂but␈α∂we␈α∂don't␈α∂yet␈α∂have␈α∂a␈α∂syntactic␈α∂way␈α∂of␈α∂minimizing␈α∂truth␈α∂values,␈α∂i.e.␈α⊂ an␈α∂axiom
␈↓ α∧␈↓schema corresponding to circumscription.

␈↓ α∧␈↓John McCarthy
␈↓ α∧␈↓Artificial Intelligence Laboratory
␈↓ α∧␈↓Stanford University
␈↓ α∧␈↓Stanford, California 94305

␈↓ α∧␈↓␈↓εThis draft of MINIMA[S77,JMC] PUBbed at 22:47 on August 3, 1978.